package leetcode.weekly.week314;

//Solution4Test
public class Solution4 {

	int m, n;
	int target;

	int mod = (int) 1e9 + 7;

	public int numberOfPaths(int[][] grid, int k) {
		m = grid.length;
		n = grid[0].length;
		target = k;
		return (int) (this.f(grid, 0, 0, k) % mod);
	}

	private long f(int[][] grid, int x, int y, int k) {
		if (x == m || y == n) {
			return 0;
		}
		if (x == m - 1 && y == n - 1) {
			if (grid[x][y] % k == 0) {
				return 1;
			}
			return 0;
		}
		long ans = 0;
		int next = (target + k - grid[x][y]) % target;
		next = next == 0 ? target : next;
		ans += this.f(grid, x + 1, y, next);
		ans += this.f(grid, x, y + 1, next);
		return ans;
	}

}
